/**
 * @link https://leetcode.cn/problems/climbing-stairs/?envType=study-plan-v2&envId=top-interview-150
 */
function climbStairs(n: number): number {
  let ans = 0;
  let p = 0;
  let q = 1;
  for (let i = 1; i < n + 1; i++) {
    ans = p + q;
    p = q;
    q = ans;
  }
  return ans;
}

/**
 * @link https://leetcode.cn/problems/house-robber/?envType=study-plan-v2&envId=top-interview-150
 */
function rob(nums: number[]): number {
  //   let dp = [];
  //   dp[0] = 0;
  //   if (!nums?.length) return 0;
  //   dp[1] = nums[0];
  //   for (let i = 1; i < nums.length; i++) {
  //     dp[i + 1] = Math.max(dp[i], dp[i - 1] + nums[i]);
  //   }
  //   console.log(dp);

  //   return dp[nums.length];
  let ans = 0;
  let p = 0;
  if (!nums?.length) return 0;
  let q = nums[0];
  for (let i = 1; i < nums.length; i++) {
    ans = Math.max(q, p + nums[i]);
    p = q;
    q = ans;
  }
  return ans;
}

/**
 * @link https://leetcode.cn/problems/word-break/?envType=study-plan-v2&envId=top-interview-150
 */
function wordBreak(s: string, wordDict: string[]): boolean {
  let dp = [];
  for (let i = 0; i < s.length + 1; i++) {
    dp[i] = false;
  }
  dp[0] = true;

  for (let i = 0; i < s.length + 1; i++) {
    // console.log(i);

    for (let j = 0; j < i; j++) {
      //   console.log(j, i, s.slice(j, i), wordDict.includes(s.slice(j, i)));
      if (dp[j] && wordDict.includes(s.slice(j, i))) {
        dp[i] = true;
        break;
      }
    }
  }
  //   console.log(dp);

  return dp[s.length];
}

/**
 * @link https://leetcode.cn/problems/coin-change/?envType=study-plan-v2&envId=top-interview-150
 */
function coinChange(coins: number[], amount: number): number {
  let dp = [];
  for (let i = 0; i < amount + 1; i++) {
    dp[i] = -1;
  }
  dp[0] = 0;
  for (let i = 1; i < amount + 1; i++) {
    for (let j = 0; j <= i / 2; j++) {
      console.log(i, i / 2, j, i - j);
      if (j === 0) {
        if (coins.includes(i)) {
          console.log("可以直接拿", i);

          dp[i] = 1;
          break;
        }
      } else {
        if (dp[j] !== -1 && dp[i - j] !== -1) {
          dp[i] =
            dp[i] === -1
              ? dp[j] + dp[i - j]
              : Math.min(dp[i], dp[j] + dp[i - j]);
        }
      }
    }
  }
  console.log(dp);

  return dp[amount];
}

/**
 * @link https://leetcode.cn/problems/longest-increasing-subsequence/?envType=study-plan-v2&envId=top-interview-150
 */
function lengthOfLIS(nums: number[]): number {
  let dp = Array(nums.length).fill(1);
  for (let i = 1; i < nums.length; i++) {
    for (let j = 0; j < i; j++) {
      console.log(j, i);

      if (nums[j] < nums[i]) {
        dp[i] = Math.max(dp[j] + 1, dp[i]);
      }

      console.log(dp);
    }
  }
  console.log(dp);

  return Math.max(...dp);
}

export default { climbStairs, rob, wordBreak, coinChange, lengthOfLIS };
